package com.cqs.leetcode;

import com.google.common.base.Stopwatch;

import java.time.Duration;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Author:li
 * <p>
 * create date: 18-5-26 08:04
 */
public class LetterCombinationsPhoneNumber17 {


    //0ms
    static class Solution1 {
        static String[] digitChars = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        private List<String> result = new ArrayList<>();

        public List<String> letterCombinations(String digits) {
            if (digits == null || digits.length() == 0) return new ArrayList<>();
            dfs(digits, 0, new StringBuilder());
            return result;
        }

        private void dfs(String digits, int level, StringBuilder tmp) {
            if (level >= digits.length()) {
                result.add(tmp.toString());
                return;
            }
            int idx = digits.charAt(level) - '2';
            String chars = digitChars[idx];
            for (int j = 0; j < chars.length(); j++) {
                //放该字符
                tmp.append(chars.charAt(j));
                dfs(digits, level + 1, tmp);
                //不放该字符
                tmp.deleteCharAt(tmp.length() - 1);
            }
        }

    }

    //7ms
    static class Solution2 {

        //数字和字母的映射关系
        String[] digitChars = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        public List<String> letterCombinations(String digits) {
            if (digits == null || digits.length() == 0) return new ArrayList<>();
            List<String> list = new ArrayList<>();
            list.add("");
            //DP
            for (int i = 0; i < digits.length(); i++) {
                String chars = digitChars[digits.charAt(i) - '2'];
                List<String> tmp = list;
                list = new ArrayList<>();
                for (int j = 0; j < chars.length(); j++) {
                    for (String s : tmp) {
                        list.add(s + chars.charAt(j));
                    }
                }
            }
            return list;
        }
    }


    public static void main(String[] args) {
        Solution1 solution = new Solution1();
        Solution2 ln = new Solution2();
        String str = "23456789";
        str = "234567892";
        Stopwatch sw = Stopwatch.createStarted();
        List<String> list0 = solution.letterCombinations(str);
        sw.stop();
        Duration elapsed = sw.elapsed();
        sw.reset();
        sw.start();
        List<String> list = ln.letterCombinations(str);
        sw.stop();
        Duration elapsed1 = sw.elapsed();

        list.removeAll(list0);
        System.out.println(elapsed + "\t" + elapsed1 + "\t" + list.size());
    }

}
